#include <iostream>
#include <vector>
#include <cmath> // 用于 sqrt
using namespace std;

// 素数表：primes[x]表示x是否为素数
vector<bool> primes;

// 工具方法：判断x是否素数
// 本题中需要反复检查两数之和是否为素数，而且范围为20以内的数相加
// 因此考虑用打表法提高查找效率
bool isPrime(int x) {
    // 初始化素数表
    if (primes.empty()) {
        primes.resize(42, true);
        for (int i = 2; i < 42; i++)
            if (primes[i])
                for (int j = i * 2; j < 40; j += i)
                    primes[j] = false;
    }
    return primes[x];
}

// 检查当前填充是否满足素数环规则
bool check(int k, const vector<int>& a, int n) {
    // 检查是否有重复数字
    for (int i = 0; i < k; ++i) {
        if (a[i] == a[k]) return false;
    }

    // 检查相邻数字之和是否为素数
    if (!isPrime(a[k] + a[k - 1])) return false;

    // 如果是最后一个数字，检查首尾之和是否为素数
    if (k == n - 1 && !isPrime(a[k] + a[0])) return false;

    return true;
}

// 回溯法求解素数环问题
void primeCircle(int n) {
    // 用数组表示素数环，并初始化为0
    vector<int> a(n, 0);
    a[0] = 1; // 第一个位置放置1
    int k = 1; // 当前填充的位置

    // 执行回溯
    while (k >= 1) {
        a[k]++;
        while (a[k] <= n) {
            if (check(k, a, n)) break;
            a[k]++;
        }

        if (a[k] <= n && k == n - 1) {
            // 找到一个解，输出
            for (int j = 0; j < n; ++j) {
                cout << a[j] << " ";
            }
            cout << endl;
            return;
        }

        if (a[k] <= n && k < n - 1) {
            k++; // 尝试填充下一个位置
        } else {
            a[k--] = 0; // 回溯
        }
    }
}

int main() {
    int n = 20; // 素数环的大小
    primeCircle(n);
    return 0;
}